"""
Problem 102: https://projecteuler.net/problem=102

Three distinct points are plotted at random on a Cartesian plane,
for which -1000 ≤ x, y ≤ 1000, such that a triangle is formed.

Consider the following two triangles:

A(-340,495), B(-153,-910), C(835,-947)

X(-175,41), Y(-421,-714), Z(574,-645)

It can be verified that triangle ABC contains the origin, whereas
triangle XYZ does not.

Using triangles.txt (right click and 'Save Link/Target As...'), a 27K text
file containing the coordinates of one thousand "random" triangles, find
the number of triangles for which the interior contains the origin.

"""

from collections import namedtuple


DataFile = 'p102_triangles.txt'

Point = namedtuple('Point', ['x', 'y'])
Triangle = namedtuple('Triangle', ['A', 'B', 'C'])


def readData(filepath: str = DataFile) -> list:
    data = []
    with open(filepath, 'r') as fp:
        for line in fp:
            linedata = eval('[' + line.strip() + ']')
            iTriangle = Triangle(
                Point(linedata[0], linedata[1]),
                Point(linedata[2], linedata[3]),
                Point(linedata[4], linedata[5]))
            data.append(iTriangle)

    return data


Data = readData(DataFile)


def hasOrigin(tri: Triangle):
    '''
    line equation: (y-y1)/(x-x1) = (y2-y1)/(x2-x1)

    >>> assert hasOrigin(Triangle(Point(0,0), Point(0,1), Point(1,1)))
    >>> assert hasOrigin(Triangle(Point(-340,495), Point(-153,-910), Point(835,-947)))
    >>> assert not hasOrigin(Triangle(Point(-175,41), Point(-421,-714), Point(574,-645)))
    '''

    def sameside(A, B, C, P):
        '''
        C, P at same side for line AB

        line AB: (B.x-A.x) * y - (B.y-A.y) * x- (B.x-A.x)*A.y + (B.y-A.y)*A.x = 0
        '''

        ec = (B.x-A.x)*C.y - (B.y-A.y)*C.x - (B.x-A.x)*A.y + (B.y-A.y)*A.x
        e0 = (B.x-A.x)*P.y - (B.y-A.y)*P.x - (B.x-A.x)*A.y + (B.y-A.y)*A.x

        return ec*e0 >= 0

    return all((sameside(tri.A, tri.B, tri.C, Point(0, 0)),
               sameside(tri.B, tri.C, tri.A, Point(0, 0)),
               sameside(tri.C, tri.A, tri.B, Point(0, 0))))


def solution(data: list = Data) -> int:
    """
    the number of triangles for which the interior contains the origin
    """
    return sum(hasOrigin(t) for t in data)


if __name__ == "__main__":
    from doctest import testmod

    testmod()
    print(solution())
    # 228
